/*
Given a sorted array a. Find the longest arithmetic progression.
Ex. 1 2 3 4 6 8 10 11 12 13 14 16 18.
The longest arithmetic progression is 2 4 6 8 10 12 14 16 18.
Sol: It’s a typical dynamic programming problem. We define 2-dimension state variable d(i,j) to denote the largest length of arithmetic progression which start with a[i], a[j]. So we initialize d(i,j) to 2. The logic here is straightforward: we scan a[j] from end to start and see the difference between a[j]-a[i] and a[k]-a[j] (i<j<k). If a[j]-a[i]>a[k]-a[j], we try larger one (k++); if a[j]-a[i]<a[k]-a[j] , that means we can’t extend arithmetic progression from a[i] a[j] any more. If a[j]-a[i]=a[k]-a[j], we update d[i][j] and max length. */

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

int d[15][15];

int getLongestArth(int a[], int size)
{
    int maxlen = 2;
    for (int i = 0; i < size; i++) {
	for (int j = i+1; j < size; j++)
	    d[i][j] = 2;
    }
    
    for (int j = size-1; j >= 0; j--) {
	int i = j-1, k = j+1;

	while (i >= 0 && k < size) {
	    if (a[j] - a[i] > a[k] - a[j]) {
		k++;
	    } else if (a[j] - a[i] < a[k] - a[j]) {
		i--;
	    } else {
		d[i][j] = d[j][k] +1;
		maxlen = max(maxlen, d[i][j]);
		i--;
		k++;
	    }
	}
    }
    for (int i = 0; i < size; i++) {
	for (int j = 0; j < size; j++)
	    cout << d[i][j] << " ";
	cout << endl;
    }
    return maxlen;
}

int getLongestArth2(int a[], int size)
{
    int maxlen = 2;
    for (int i = 0; i < size; i++) {
	for (int j = i+1; j < size; j++)
	    d[i][j] = 2;
    }
    
    for (int j = 1; j < size; j++) {
	int i = j-1, k = j+1;

	while (i >= 0 && k < size) {
	    if (a[j] - a[i] > a[k] - a[j]) {
		k++;
	    } else if (a[j] - a[i] < a[k] - a[j]) {
		i--;
	    } else {
		d[j][k] = d[i][j] +1;
		maxlen = max(maxlen, d[j][k]);
		i--;
		k++;
	    }
	}
    }
    for (int i = 0; i < size; i++) {
	for (int j = 0; j < size; j++)
	    cout << d[i][j] << " ";
	cout << endl;
    }
    return maxlen;
}

int main(int argc, char **argv)
{
    int a[] = {1, 2, 3, 4, 6, 8, 10, 11, 12, 13, 14, 16, 18};
//    int a[] = {2,3,5,7,8,11};
    cout << getLongestArth(a, sizeof(a)/sizeof(int)) << endl;
    cout << getLongestArth2(a, sizeof(a)/sizeof(int)) << endl;
}
